lib/Mi manual de algoritmos/version_world_finals_2009/src/estructuras/#fenwick.tex#

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{Blue}{class}}\ FenwickTree\textcolor{Red}{\{} \\
   6 \mbox{}\ \ vector\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\textcolor{BrickRed}{$>$}\ v\textcolor{BrickRed}{;} \\
   7 \mbox{}\ \ \textcolor{ForestGreen}{int}\ maxSize\textcolor{BrickRed}{;} \\
   8 \mbox{} \\
   9 \mbox{}\textbf{\textcolor{Blue}{public}}\textcolor{BrickRed}{:} \\
  10 \mbox{}\ \ \textbf{\textcolor{Black}{FenwickTree}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ $\_$maxSize\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{:}\ \textbf{\textcolor{Black}{maxSize}}\textcolor{BrickRed}{(}$\_$maxSize\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textcolor{Red}{\{} \\
  11 \mbox{}\ \ \ \ v\ \textcolor{BrickRed}{=}\ vector\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\textcolor{BrickRed}{$>$(}maxSize\textcolor{BrickRed}{,}\ 0LL\textcolor{BrickRed}{);} \\
  12 \mbox{}\ \ \textcolor{Red}{\}} \\
  13 \mbox{} \\
  14 \mbox{}\ \ \textcolor{ForestGreen}{void}\ \textbf{\textcolor{Black}{add}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ where\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ what\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  15 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}where\textcolor{BrickRed}{++;}\ where\ \textcolor{BrickRed}{$<$=}\ maxSize\textcolor{BrickRed}{;}\ where\ \textcolor{BrickRed}{+=}\ where\ \textcolor{BrickRed}{\&}\ \textcolor{BrickRed}{-}where\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  16 \mbox{}\ \ \ \ \ \ v\textcolor{BrickRed}{[}where\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+=}\ what\textcolor{BrickRed}{;} \\
  17 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  18 \mbox{}\ \ \textcolor{Red}{\}} \\
  19 \mbox{} \\
  20 \mbox{}\ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ where\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  21 \mbox{}\ \ \ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ sum\ \textcolor{BrickRed}{=}\ v\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{];} \\
  22 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}where\textcolor{BrickRed}{++;}\ where\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ where\ \textcolor{BrickRed}{-=}\ where\ \textcolor{BrickRed}{\&}\ \textcolor{BrickRed}{-}where\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  23 \mbox{}\ \ \ \ \ \ sum\ \textcolor{BrickRed}{+=}\ v\textcolor{BrickRed}{[}where\textcolor{BrickRed}{];} \\
  24 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  25 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ sum\textcolor{BrickRed}{;} \\
  26 \mbox{}\ \ \textcolor{Red}{\}} \\
  27 \mbox{} \\
  28 \mbox{}\ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ from\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ to\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  29 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}to\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{-}\ \textbf{\textcolor{Black}{query}}\textcolor{BrickRed}{(}from\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{);} \\
  30 \mbox{}\ \ \textcolor{Red}{\}} \\
  31 \mbox{} \\
  32 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  33
  34 } \normalfont\normalsize